/**
 * @file bi_tree_array.cpp
 * @brief 二叉树的顺序结构实现
 * @author Xavier ZXY (zxy_xavier@163.com)
 * @version : 1.0
 * @date 2022-05-18
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include "bi_tree_array.h"

int main(int argc, char const *argv[])
{
    Status i;
    Position p;
    TElemType e;
    SqBiTree T;
    InitBiTree(T);
    CreateBiTree(T);
    printf("建立二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n", BiTreeEmpty(T), BiTreeDepth(T));
    i = Root(T, &e);
    if (i)
        printf("二叉树的根为：%d\n", e);
    else
        printf("树空，无根\n");
    printf("层序遍历二叉树:\n");
    LevelOrderTraverse(T);
    printf("前序遍历二叉树:\n");
    PreOrderTraverse(T);
    printf("中序遍历二叉树:\n");
    InOrderTraverse(T);
    printf("后序遍历二叉树:\n");
    PostOrderTraverse(T);
    printf("修改结点的层号3本层序号2。");
    p.level = 3;
    p.order = 2;
    e = Value(T, p);
    printf("待修改结点的原值为%d请输入新值:50 ", e);
    e = 50;
    Assign(T, p, e);
    printf("前序遍历二叉树:\n");
    PreOrderTraverse(T);
    printf("结点%d的双亲为%d,左右孩子分别为", e, Parent(T, e));
    printf("%d,%d,左右兄弟分别为", LeftChild(T, e), RightChild(T, e));
    printf("%d,%d\n", LeftSibling(T, e), RightSibling(T, e));
    ClearBiTree(T);
    printf("清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n", BiTreeEmpty(T), BiTreeDepth(T));
    i = Root(T, &e);
    if (i)
        printf("二叉树的根为：%d\n", e);
    else
        printf("树空，无根\n");

    return 0;
}


Status visit(TElemType c) {
    printf("%d", c);
    return OK;
}

/**
 * @brief 构造空二叉树
 */
Status InitBiTree(SqBiTree T) {
    for (int i = 0; i < MAX_TREE_SIZE; i ++) {
        T[i] = Nil;
    }

    return OK;
}

/**
 * @brief 按照层序顺序输入二叉树中结点的值，构造顺序存储的二叉树
 */
Status CreateBiTree(SqBiTree T) {
 	printf("请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≤%d:\n",MAX_TREE_SIZE);
    int i = 0;
    
    while (i < 10) {
        T[i] = i + 1;
        if (i!=0 && T[(i+1)/2-1]==Nil && T[i]!=Nil) {
            printf("出现了无双亲的非根节点%d\n", T[i]);
            exit(ERROR);
        }
        i ++;
    }

    while (i < MAX_TREE_SIZE) {
        T[i] = Nil;
        i ++;
    }

    return OK;
}

#define ClearBiTree InitBiTree  //清空二叉树

/**
 * @brief 二叉树是否为空
 */
Status BiTreeEmpty(SqBiTree T) {
    if (T[0] == Nil)
        return TRUE;
    else
        return FALSE;
}

/**
 * @brief 返回二叉树T的深度
 */
int BiTreeDepth(SqBiTree T) {
    int i = MAX_TREE_SIZE - 1;
    for ( ;i >= 0; i --) {
        if (T[i] != Nil)
            break;
    }
    i ++;
    int j = -1;
    do
    {
        j ++;
    } while (i >= powl(2, j));

    return j;
}

/**
 * @brief 返回二叉树的根结点
 */
Status Root(SqBiTree T, TElemType *e) {
    if (BiTreeEmpty(T))
        return ERROR;
    else {
        *e = T[0];
    }

    return OK;
}

/**
 * @brief 返回e位置对应的结点值
 */
TElemType Value(SqBiTree T, Position e) {
    return T[(int)powl(2, e.level-1) + e.order - 2];
}

/**
 * @brief 二叉树存在，将处于位置e的结点赋予新值
 */
Status Assign(SqBiTree T, Position e, TElemType value) {
    int i = (int)powl(2, e.level-1) + e.order - 2;
    if (value != Nil && T[(i + 1)/2-1 == Nil])  //给叶子节点赋非空值，但双亲结点为空
        return ERROR;
    else if (value == Nil && (T[i*2+1] != Nil || T[i*2+2] != Nil))  //给结点赋空值，但孩子节点不为空
        return ERROR;
    
    T[i] = value;

    return OK;
}

/**
 * @brief 返回e结点的双亲结点
 */
TElemType Parent(SqBiTree T, TElemType e) {
    if (BiTreeEmpty(T))
        return Nil;
    for (int i = 1; i <= MAX_TREE_SIZE - 1; i ++) {
        if(T[i] == e)
            return T[(i+1)/2 - 1];
    }

    return Nil;
}

/**
 * @brief 返回这个结点的左孩子
 */
TElemType LeftChild(SqBiTree T, TElemType e) {
    if (T[0] == Nil)
        return Nil;
    
    for (int i = 0; i <= MAX_TREE_SIZE - 1; i ++) {
        if (T[i] == e)
            return T[i*2+1];
    }

    return Nil;
}

/**
 * @brief 返回结点值为e的右孩子
 */
TElemType RightChild(SqBiTree T, TElemType e) {
    if (T[0] == Nil)
        return Nil;
    for (int i = 0; i < MAX_TREE_SIZE; i ++) {
        if (T[i] == e)
            return T[i*2+2];
    }

    return Nil;
}

/**
 * @brief 左兄弟
 */
TElemType LeftSibling(SqBiTree T, TElemType e) {
    if (T[0] == Nil)
        return Nil;
    for (int i = 1; i < MAX_TREE_SIZE; i ++) {
        if (T[i] == e && i % 2 ==0)  //找到e且序号为偶数(右孩子)
            return T[i - 1];
    }

    return Nil;
}

/**
 * @brief 返回e的右兄弟
 */
TElemType RightSibling(SqBiTree T, TElemType e) {
    if (T[0] == Nil)
        return Nil;
    for (int i = 1; i < MAX_TREE_SIZE; i ++) {
        if (T[i] == e && i % 2)  //找到e且序号为奇数(左孩子)
            return T[i + 1];
    }

    return Nil;
}

/**
 * @brief 前序遍历
 */
void PreTraverse(SqBiTree T,int e) {
    visit(T[e]);
    if (T[2*e + 1] != Nil)
        PreTraverse(T, 2*e+1);
    if (T[2*e + 2] != Nil)
        PreTraverse(T, 2*e+2);
}
Status PreOrderTraverse(SqBiTree T) {
    if (!BiTreeEmpty(T))
        PreTraverse(T, 0);
    printf("\n");

    return OK;
}

/**
 * @brief 中序遍历
 */
void InTraverse(SqBiTree T,int e) {
    if (T[2*e+1] != Nil)
        InTraverse(T, 2*e+1);
    visit(T[e]);
    if (T[2*e+2] != Nil)
        InTraverse(T, 2*e+2);
}
Status InOrderTraverse(SqBiTree T) {
    if (!BiTreeEmpty(T))
        InTraverse(T, 0);
    printf("\n");

    return OK;
}

/**
 * @brief 后序遍历            
 */
void PostTraverse(SqBiTree T,int e) {
    if(T[2*e+1]!=Nil) /* 左子树不空 */
		PostTraverse(T,2*e+1);
	if(T[2*e+2]!=Nil) /* 右子树不空 */
		PostTraverse(T,2*e+2);
	visit(T[e]);
}
Status PostOrderTraverse(SqBiTree T) {
    if(!BiTreeEmpty(T)) /* 树不空 */
		PostTraverse(T,0);
	printf("\n");
	return OK;
}

// 层序遍历
void LevelOrderTraverse(SqBiTree T) {
    int i=MAX_TREE_SIZE-1,j;
	while(T[i]==Nil)
		i--; /* 找到最后一个非空结点的序号 */
	for(j=0;j<=i;j++)  /* 从根结点起,按层序遍历二叉树 */
		if(T[j]!=Nil)
			visit(T[j]); /* 只遍历非空的结点 */
	printf("\n");
}

//逐层,按本层序号输出二叉树
void Print(SqBiTree T) {
    int j,k;
	Position p;
	TElemType e;
	for(j=1;j<=BiTreeDepth(T);j++)
	{
		printf("第%d层: ",j);
		for(k=1;k<=powl(2,j-1);k++)
		{
			p.level=j;
			p.order=k;
			e=Value(T,p);
			if(e!=Nil)
				printf("%d:%d ",k,e);
		}
		printf("\n");
	}
}